1. Technical Field
The present application relates generally to an improved data processing system. More specifically, the present application is directed to mechanisms for performing useful computations while waiting for a line in a system with a software implemented cache.
2. Description of Related Art
A cache is a collection of data duplicating original values stored elsewhere or computed earlier. The original data that is cached is typically expensive to fetch, in terms of access time, or compute relative to reading the cache. Once the data is stored in the cache, future use can be made by accessing the cached copy rather than re-fetching or re-computing the original data. As a result, the average access time is lower.
Processor caches are generally managed entirely by hardware. Other caches are managed by a variety of software. Hardware managed caches are referred to generally as hardware caches while software managed caches are generally referred to as software caches. In either case, a hardware bank of registers is typically used to store the data for the cache.
The cache is essentially a pool of entries. Each entry has a datum, which is a copy of the datum in a backing store. Each entry also has a tag, which specifies the identity of the datum in the backing store of which the entry is a copy. When a cache client, e.g., a CPU, web browser, operating system, etc., wishes to access a datum presumably in the backing store, it first checks the cache. If an entry can be found with a tag matching that of the desired datum, the datum in the entry is used instead. This situation is known as a cache hit. The percentage of accesses that result in cache hits is known as the hit rate or hit ratio of the cache.
The alternative situation, i.e. when the cache is consulted and the datum with the desired tag is not found in the cache, is known as a cache miss. With a cache miss, the datum must be re-fetched from the backing store or otherwise re-calculated. The datum fetched from the backing store during miss handling is usually inserted into the cache, ready for the next access.
If the cache has limited storage, it may have to eject some other entry in order to make room for the re-fetched datum. The heuristic used to select the entry to eject is known as the replacement policy. One popular replacement policy, least recently used (LRU), replaces the least recently used entry.
When a datum is written to the cache, it must at some point be written to the backing store as well. The timing of this write is controlled by what is known as the write policy. In a write-through cache, every write to the cache causes a write to the backing store. Alternatively, in a write-back cache, writes are not immediately mirrored to the store. Instead, the cache tracks which of its locations have been written over (these locations are marked dirty). The data in these locations is written back to the backing store when that data is evicted from the cache. For this reason, a miss in a write-back cache will often require two memory accesses to service.
Cache misses may be very expensive to the execution of a program both in terms of the access time to re-fetch the datum that is missing in the cache as well as the lost processing ability while waiting for the re-fetched datum. That is, the process of re-fetching the datum from the backing store requires a relatively large access time in which the instructions requiring the datum must wait for the datum to be re-fetched and stored in the cache. Thus, a number of processing cycles may be lost in which useful computations may be performed but are not due to the fact that the required datum is not present in the cache.